| DFS深度优先搜索 | 您所在的位置：网站首页 › java 广度优先搜索 › DFS深度优先搜索 |
DFS深度优先搜索
|
递归三要素
递归的定义 递归的拆解 递归的出口 什么时候使用DFS？深度回溯问题（DFS与回溯区别不大） 二叉树问题 组合、排列问题 找方案问题（解空间是一棵树或者图，需要自行构造图/树） 图的搜索问题/路径/方案/节点 的的排列 不要使用DFS的场景连通块问题 拓扑排序 一切可以使用BFS解决的问题 组合问题例如，[1,2,3] 的所有组合为 [] [1] [2] [3] [1,2] [1,3] [2,3] [1,2,3] 共8种 。 问题模型：求出所有满足条件的组合判断条件：组合中的元素与顺序无关时间复杂度：2^n难点：将题目的要求构成图或者树，以本题为例，可以将集合中的元素作为节点，那么如何构建边呢？为了避免出现出现12和21这种重复集合，可以让小数节点指向大数节点形成有向边。如下图所示：
以下题目DFS不一定是好的解法，但是练手深搜是非常合适的。所有，很多时候，其实DFS属于暴力搜索算法，并不是优化算法，但是作为最基础的搜索算法，必须掌握才能在此基础上进行动态规划或者剪枝优化。 386. 字典序排数 class Solution { int[] item; int[] visit; List res; public void dfs(int[] nums,int step,int n){ if(step==n){ for(int a : item){ res.add(a); } return; } for (int i = 0; i visit[i]=1; item[step] = nums[i]; //多了这段中途判断而已 if(step>0 && ((item[step-1]+"").compareTo(item[step]+""))>0){ visit[i]=0; return; } dfs(nums,step+1,n); visit[i]=0; } } } public List lexicalOrder(int n) { item = new int[n]; visit = new int[n]; res = new ArrayList(); int[] arr = new int[n]; for (int i = 0; i int res; int sum; int visit[][]; //==================第一种写法================== public void dfs(int[][] grid,int i,int j,int summ){ if(i==(grid.length-1) && j==grid[0].length-1){ res = Math.min(res,summ); } //下走 if((i+1) visit[i][j+1]=1; dfs(grid,i,j+1,summ+grid[i][j+1]); visit[i][j+1]=0; } } //================第二种写法================ public void dfs(int[][] grid,int i,int j ){ if(i==(grid.length-1) && j==grid[0].length-1){ res = Math.min(res,sum); } //下走 if((i+1) visit[i][j+1]=1; int temp = sum; sum += grid[i][j+1]; dfs(grid,i,j+1 ); visit[i][j+1]=0; //或者 sum -= grid[i][j+1]; sum = temp;// 还原sum; } } public int minPathSum(int[][] grid) { visit = new int[grid.length][grid[0].length]; res = Integer.MAX_VALUE; sum = grid[0][0] ; dfs(grid,0,0 ); return res; } }其实，这道题也是非常好的记忆化搜索的动态规划例题，如下： class Solution { int mem[][]; public int arrive(int[][] grid,int i,int j){ if(i==0 && j==0){ return grid[i][j]; } int v1 = Integer.MAX_VALUE; int v2 = Integer.MAX_VALUE; if((i-1)>=0 && j>=0 ) { if(mem[i-1][j]==-1){ v1 = arrive(grid,i-1,j); mem[i-1][j] = v1; }else { v1 = mem[i-1][j]; } } if((j-1>=0) && i>=0){ if (mem[i][j-1]==-1){ v2 = arrive(grid,i,j-1); mem[i][j-1] = v2; }else{ v2 = mem[i][j-1]; } } return Math.min(v1,v2)+grid[i][j]; } public int minPathSum(int[][] grid) { //动态规划 mem = new int[grid.length][grid[0].length]; for (int i = 0; i mem[i][j] = -1; } } mem[0][0] = grid[0][0]; return arrive(grid,grid.length-1,grid[0].length-1); } }最后以一道典型DFS题结束本章讲解 200. 岛屿数量思路：凡是搜到了一个1，就找到了一个岛屿，为了避免重复计算，需要把这个岛（这个岛不是这个图）的所有1改成0，然后继续往下搜。简单说就是看见1就计数+1，然后把这片岛毁了，接着往下走！其实这里不用visit记录是否访问过，因为访问过的会将其标记为0，但是写了无妨！建议按照模板操作！ public class lc200 { int visit[][]; public void dfs(char[][] grid,int i , int j){ if(grid[i][j]=='0'){ //如果是水就不用深入查找了 return; } grid[i][j]='0'; //摧毁 int[][] dirc = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; //方向 上下左右 for (int k = 0; k //这里判断写的复杂，就是边界判断加访问判断 visit[i+x][j+y] = 1; if(grid[i+x][j+y]=='1'){ dfs(grid,i+x,j+y); //如果还是岛就继续深入 } visit[i+x][j+y] = 0; } } } public int numIslands(char[][] grid) { int count = 0; visit = new int[grid.length][grid[0].length]; for (int i = 0; i if(grid[i][j]=='1'){ count++; dfs(grid,i,j); //开始毁灭这个岛所有1 } } } return count; } } 推荐LeetCode类似题型463. 岛屿的周长 思路：这道题只有一个岛屿，所以可以两重循环判断1是否挨着0或者是边界，是的话就算作边，考虑上下左右，加起来就是周长。但是 如果深度搜索呢？一样的，对于每个1都计算与水或者边界相邻的边。 695. 岛屿的最大面积 思路：和统计岛屿数量相同，只不过深度遍历每个岛屿时计算有多少个1，存下来，最后返回最大值即为最大面积的岛屿。 827. 最大人工岛 以上，此题作为思考题！ |
除此之外也可以将其构建成一棵树，小节点指向大节点，如下所示： 
【本文地址】
公司简介
联系我们